#ifndef AVL_HEADER_H
#define AVL_HEADER_H


#include <cstdbool>
#include <cstdlib>
#include <cstdio>
#include <vector>
#include <stack>
#include <string>
#include <unordered_map>

enum AVL_UB_TYPE {
    AVL_LLL_UB,
    AVL_RRR_UB,
    AVL_LR_UB,
    AVL_RL_UB,
    AVL_NORMAL
};


static constexpr  char* avl_ub_strs[] = {
    "avl_lll_ub",
    "avl_rrr_ub",
    "avl_lr_ub",
    "avl_rl_ub",
    "avl_normal"
};


struct avl_node_ {
    int height;
    int val;
    struct avl_node_ *lchild;
    struct avl_node_ *rchild;
    struct avl_node_ *parent;
};

typedef struct avl_node_ avl_node;


struct avl_node_info {

    avl_node_info(int d, int v):depth_(d),val_(v) {

    }
    int depth_{};
    int val_{};
};



int avl_get_height(const avl_node *node);


avl_node * avl_make_new_node(int v);
void       avl_free_node(avl_node * node);
void   avl_unlinked_from_parent( avl_node *node);


void avl_rebalanced(avl_node *node);


avl_node * avl_rotateL(avl_node *tar);
avl_node * avl_rotateR(avl_node *tar);
avl_node * avl_rotateLR(avl_node *tar);
avl_node * avl_rotateRL(avl_node *tar);
enum AVL_UB_TYPE avl_get_ub_type(avl_node *node);
avl_node * avl_adjust(avl_node *node, enum AVL_UB_TYPE tp);


void avl_preorder_dump(const avl_node *node, int *dst, int  *pcnt);
void  avl_inorder_dump(const avl_node *node, int *dst, int  *pcnt);
void  avl_postorder_dump(const avl_node *node, int *dst, int  *pcnt);

void avl_preorder_dump(const avl_node *node, std::vector<int> &echo);

void avl_inorder_dump(const avl_node *node, std::vector<int> &echo);
void avl_postorder_dump(const avl_node *node, std::vector<int> &echo);
void avl_echo_ub_type(enum AVL_UB_TYPE tp);

bool avl_insert(avl_node **root, int target);
avl_node * avl_find_node(avl_node **root, int target);
bool avl_find( avl_node **root, int target);

bool avl_delete( avl_node **root, int target);

avl_node * avl_get_rep_node( avl_node * delete_node );

void avl_update_new_tree_root(avl_node ** root);



bool avl_verify(const avl_node *root);
#endif